package william.list;

/**
 * @author ZhangShenao
 * @date 2024/1/15
 * @description <a href="https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/">...</a>
 */
public class Leetcode_面试题02_02_返回倒数第k个节点 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 使用快、慢双指针法
     * Step1: 将快指针先前进k-1个节点
     * Step2: 将快、慢指针同时前进,每次前进1个节点
     * Step3: 当快指针移动到链表最后一个节点时,慢指针即指向倒数第k个节点
     */
    public int kthToLast(ListNode head, int k) {
        //边界条件校验
        if (head == null || k <= 0) {
            throw new IllegalArgumentException("illegal input!!");
        }

        //采用快、慢指针
        ListNode fast = head;
        ListNode slow = head;

        //首先将快指针前进k-1个节点
        int i = 0;
        while (i < k - 1 && fast != null) {
            fast = fast.next;
            i++;
        }
        if (fast == null) {
            throw new IllegalArgumentException("illegal input!!");
        }

        //然后将快、慢指针同时前进,每次前进1个节点
        //当快指针移动到链表最后一个节点时,慢指针即指向倒数第k个节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        if (slow == null) {
            throw new IllegalArgumentException("illegal input!!");
        }
        return slow.val;
    }
}
